﻿namespace CSP

module Domain =

    /// The domain of possible values for a variable in a CSP problem.
    type 'a domain =
        abstract member Count: int
        abstract member Values: 'a list

    type private 'a list_domain(list) =
        let count = List.length list
        override d.ToString() = sprintf "Domain %A" list
        interface 'a domain with
            member d.Count = count
            member d.Values = list

    let internal count (domain: _ domain) = domain.Count
    let internal values (domain: _ domain) = domain.Values
        
    /// Creates a domain from a list of values.
    let ofList list = new list_domain<_>(list) :> _ domain

    /// Creates a domain from a sequence of values.
    let ofSeq (seq: #seq<_>) = ofList <| List.ofSeq seq

    let rec private split_list list =
        match list with
            | [] -> ([], [])
            | [x] -> ([x], [])
            | x::y::zs -> let xs, ys = split_list zs in (x::xs, y::ys)

    let internal split domain = let l, r = domain |> values |> split_list in ofList l, ofList r

    type internal 'a reduction =
            | NoReduction
            | Contradiction
            | Unique of 'a
            | Reduced of 'a domain

    let internal reduce left constr right =
        let filter = fun x -> right |> values |> List.exists (fun y -> constr x y)
        let l = left |> values |> List.filter filter
        match List.length l with
            | 0 -> Contradiction
            | c -> if c = count left then NoReduction
                   elif c = 1 then Unique (List.head l)
                   else Reduced (ofList l)

    let internal single domain =
        match values domain with
            | [x] -> x
            | _ -> failwithf "Domain does not contain exactly one element: %A." domain

    let internal filter pred domain = domain |> values |> List.filter pred |> ofList
